package Graph;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;

public class Dijkstra {
    /*用来记录理解,B站左成云老师的算法与数据结构
    * 本类主要完成,迪杰特斯拉算法---用于有向图的最短路径算法
    * 这个可以优化,比如使用堆,但是堆也得优化*/
    public static HashMap<Node,Integer> dijkstral(Node head){
        /*从head出发到所有点的最下举例
        * key : 表示从head出发到达 key
        * value : 从 head出发 到达 key的最小距离
        * 如果在表中,没有T的记录,含义就是从head出发到T这个点的距离为正无穷*/
        HashMap<Node,Integer> distanceMap=new HashMap<Node, Integer>();

        distanceMap.put(head,0);
        //已经求过距离的节点,存在selectedNodes中,以后再也不碰
        HashSet<Node> selectNodes =new HashSet<Node>();

        Node minNode = getMinDistanceAndUnselectdeNode(distanceMap,selectNodes);
        //一开始会把头结点选出来
        //getMinDistanceAndUnselectdeNode指从distanceMap找到一个最下的距离,但这个距离节点不能是选过的
        while (minNode != null){
            int distance = distanceMap.get(minNode);//拿到最小的点的距离
            for (Edge edge: minNode.edges) {
                Node toNode = edge.to ;
                if (!distanceMap.containsKey(toNode)){
                    distanceMap.put(toNode,distance+edge.weight);//把这个点所有未存在的边(正无穷)存进去
                }
                distanceMap.put(edge.to,Math.min(distanceMap.get(toNode),distance+edge.weight));
                //判断 之前的距离和现在的距离那个小入那个
            }
            selectNodes.add(minNode);//将这个点锁死不再用了
            minNode =getMinDistanceAndUnselectdeNode(distanceMap,selectNodes);
        }
        return distanceMap;
    }
    public static Node getMinDistanceAndUnselectdeNode(
            HashMap<Node,Integer> distanceMap,HashSet<Node> touchedNodes){
        Node minNode=null;
        int minDistance = Integer.MAX_VALUE;
        for (Map.Entry<Node,Integer> entry:distanceMap.entrySet()){
            Node node =entry.getKey();//遍历点
            int distance =entry.getValue();//距离拿出来
            if (!touchedNodes.contains(node) && distance < minDistance){
                minNode =node;
                minDistance=distance;
            }
        }
        return minNode;
    }




    /*改进后的迪杰特斯拉算法
    * 从head出发,所有能到达的节点,生成到达每个节点的最小路径并返回
    * key 代表*/
    public static class NodeHeap{
        private Node[] nodes;
        private HashMap<Node,Integer> heapIndexMap;
        //heapIndexMap查node在堆上的那个位置
        private HashMap<Node,Integer> distanceMap;
        //distanceMap  node到head的最短距离的值
        private int size;//堆上有几个节点

        public NodeHeap(int size){
            nodes = new Node[size];
            heapIndexMap = new HashMap<>();
            distanceMap = new HashMap<>();
            this.size =0;
        }
        public boolean isEmpty(){
            return size == 0;
        }
        public void addOrUpadateOrIgnore(Node node,int distance){
            if (inHeap(node)){
                //如果heap 在堆上
                distanceMap.put(node,Math.min(distanceMap.get(node),distance));
                //把node 更新最小举例
                insertHeapify(node,heapIndexMap.get(node));
                //向上调整

            }
            if (!isEntered(node)){
                //如果一个节点没进过堆
                //创建节点,放入进去数组与哈希表中
                nodes[size] = node;
                heapIndexMap.put(node,size);
                distanceMap.put(node,distance);
                insertHeapify(node,size++);
                //向上调整
            }
        }
        public NodeRecord pop(){

            NodeRecord nodeRecord = new NodeRecord(nodes[0],distanceMap.get(nodes[0]));
            swap(0,size-1);//干掉堆顶
            //调整哈希表
            heapIndexMap.put(nodes[size-1],-1);
            distanceMap.remove(nodes[size-1]);
            //在堆上释放掉这个节点
            nodes[size-1] = null;
            //向下调整
            heapify(0,--size);
            return nodeRecord;
        }
        private void insertHeapify(Node node,int index){
            while (distanceMap.get(nodes[index]) < distanceMap.get(nodes[(index-1)/2])){
                swap(index,(index-1)/2);
                index = (index-1)/2;
            }
        }
        private void heapify(int index,int size){
            int left = index*2 +1;
            while (left < size){
                //选择左右孩子的俩个其中的较小值
                int smallest =left + 1 < size && distanceMap.get(nodes[left+1]) < distanceMap.get(nodes[left])
                        ? left+1 : left;
                smallest = distanceMap.get(nodes[smallest]) < distanceMap.get(index)?index:smallest;
                if (smallest == index){
                    break;
                }
                swap(smallest,index);
                index = smallest;
                left = index *2 +1;
            }
        }
        private boolean isEntered(Node node){
            //指node 进没进来过这个堆中
            return heapIndexMap.containsKey(node);
        }
        private boolean inHeap(Node node){
            //标记这个节点进来过,但不在堆上所以标记为-1
            return isEntered(node) && heapIndexMap.get(node) != -1;

        }
        private void swap(int index1 , int index2){
            /*在这个堆上俩个节点要换位置,数组要换位置,哈希表也要改*/
            heapIndexMap.put(nodes[index1],index2);
            heapIndexMap.put(nodes[index2],index1);
            Node tmp = nodes[index1];
            nodes[index1] = nodes[index2];
            nodes[index2] = tmp;
        }
    }

    public static class NodeRecord{

        public Node node;
        public int distance;//到唯一出发点head的最短距离

        public NodeRecord(Node node, int distance) {
            this.node = node;
            this.distance = distance;
        }
    }
    public static HashMap<Node,Integer> dijkstra2(Node head,int size){
        NodeHeap  nodeHeap= new NodeHeap(size);
        //堆得大小不要超过size
        nodeHeap.addOrUpadateOrIgnore(head,0);
        //到本身的距离 0
        //如果有一个点的记录是第一次出现 add,如果值更小 update 如果不小,就Ignore

        HashMap<Node,Integer> result=new HashMap<>();
        while (!nodeHeap.isEmpty()){
            NodeRecord record =nodeHeap.pop();
            /*NodeRecord 代表弹出的最小值节点*/
            Node cur = record.node;
            int distance = record.distance;
            for (Edge edge : cur.edges){
                //遍历边集来更新(除之前用过节点的)距离,
                nodeHeap.addOrUpadateOrIgnore(edge.to,edge.weight+distance);
            }
            result.put(cur,distance);
        }
        return result;
    }


}
